This invention deals generally with the routing of communication paths within complex multi-nodal communication networks. In particular, the invention addresses the routing of the shortest protected paths in such networks and discloses methods for identifying and discarding paths that are unprotectable.
The Shortest Path Tree (SPT) or Dijkstra""s algorithm is a procedure used in link state protocol networks to optimize routing by finding the shortest path, or least cost path, between two network elements. A path between any two network elements, or nodes, consists of individual and contiguous path segments that begin at the source node and terminate on the target node. Path segments consist of individual and contiguous links. A link is a communications channel between two adjacent nodes. Given network nodes, which are connected by links, the question arises as to which is the shortest path between any two nodes, A and B. The term xe2x80x9cshortest pathxe2x80x9d is relative to the cost metric, which is defined for the links and path segments that are part of the network. For example, the monthly cost of an optical link operating at Optical Carrier (OC)-3 could represent a cost metric. The shortest path is that path between two network elements which has the least cost, where the cost is the sum of the predefined costs of traversing each link or path segment in the path.
Dijkstra""s algorithm, or SPT algorithm, is well known to those skilled in the art as a method for determining the shortest path between two network elements and is described in Routing in the Internet, authored by Christian Huitema, published by Prentice Hall, 1995, which is herein incorporated by reference. The process flow of Dijkstra""s SPT algorithm for determining the shortest path between one network element, the source node, and all other network elements or nodes in the network is illustrated in FIG. 1. FIG. 2 shows a simplified representation of a four-node network, and the associated link metrics. FIG. 3 shows a table illustrating the step by step execution of Dijkstra""s SPT algorithm as shown in FIG. 1, on the network shown in FIG. 2, with node N1 as the source node. There is a new shortest path at each step, which is added to the shortest path tree, while there are still unevaluated nodes.
In addition to the least cost or shortest path analysis, many communication networks require a high level of reliability. In such networks, a communication failure is relatively intolerable, and the need to insure adequate redundancy of communication channels in the event of failure is paramount. Synchronous Optical Networks (SONETs) and Synchronous Digital Hierarchy (SDH) networks are examples of such networks. When used herein, the term SONET is meant to include both SONET and SDH, the terms SONET and SDH being used interchangeably. Due to the nature of a SONET, the probability of a link or span failure due to a fiber cut, or other network element failure is significant enough to warrant the routing of protection circuits. Establishing protection insures that in the event that the primary communication circuit fails, there is alternate predefined circuit available to be used such that minimal interruption of service occurs.
For routing protected circuits in SONETs, it is useful to think of the path taken by circuits as comprised of path segments. Each path segment in the circuit is protected either due to the fact that each of the lines used by the segment is inherently protected, or by a redundant or back-up path segment. In a first instance, known as line protection, there is a redundant line or link for each link in a path. If the link fails for any reason, the network traffic traversing that failed link is switched to the redundant link. Line protection schemes such as Bi-directional Line Switched Rings (BLSR), the linear 1+1, and others are well known to those skilled in the art. In a second instance, that of path protection, the path itself is protected due to the existence of a predefined alternative path, which functions as a redundant path to be used in the event of failure of any part of the primary path segment. The primary path and its corresponding predefined alternative path, as a pair, represent an example of path protection. Path protection schemes such as Uni-directional Path Switched Rings (UPSR) are also well known to those skilled in the art. Path protection can also be thought of at the path segment level. Since a path can be thought of as a number of contiguous path segments, with some segments inherently protected while others are unprotected, it becomes desirable to establish protection for the unprotected path segments.
Establishing path protection entails establishing path segment protection for each unprotected path segment. This requires finding an alternate path segment which is referred to as a Virtual UPSR in SONET terminology. Each Path Switched Segment (PSS) is made up of a primary path segment and an alternate path segment. The two segments together form the Protected Path Switch Segment (PPSS). Further details regarding SONET protection schemes can be found in Bellcore specifications GR-253-CORE, GR-1400-CORE, and GR-1230-CORE, which are incorporated herein by reference. Typically, when provisioning circuits for network traffic, paths which are not protected are identified as such. These unprotected paths contain path segments that are not part of any inherent protection scheme. For instance, if the path segment itself is not part of a predefined path protection scheme, or if the segment contains individual links that are not part of a line protection scheme, the path is unprotected. For these unprotected paths, if an alternate edge disjoint path can be found which connects the same two nodes, then this alternate path can be used as the redundant back-up path, and the original path can be defined as being path protected. This is a way to ensure that every path segment within a path is protected.
Networks in general, and SONETs in particular, may be configured to use, among others, Dijkstra""s SPT algorithm to determine shortest paths for routing information between any two network elements. However, the SPT algorithm routes traffic based on the shortest path between nodes and does not account for or insure that the routed path is protected. The paths found by Dijkstra""s SPT algorithm between two distant network elements are comprised of path segments between the intervening network elements. Some of these segments may be inherently protected due to the SONET configuration (BLSW, 1+1, UPSR, etc.), but other segments may be unprotected. Because protection may be a critical requirement in the provisioning of circuits, particularly in SONETs, there is the desire to obtain not only the shortest path between two network elements but the shortest protected path between those elements. One approach to finding the shortest protected path is now described. First, the shortest path is found using Dijkstra""s SPT algorithm. Then, a determination is made as to whether or not the given path is protected. More specifically, a determination is made as to which path segments are not protected. If, as is common, one or more path segments are found to be unprotected, a search for an alternate path segment, or edge disjoint path segment, is made in order to provide redundancy protection for the unprotected segment. If an alternate edge disjoint path segment is found for the unprotected primary path segment, then that primary path segment can be defined as protected. If each unprotected path segment in a given path can be protected by means of finding an alternate path segment, then the entire path can be defined as protected. FIG. 4 shows a process for defining protected paths within a network. Given a network of linked network elements, and desiring to find the shortest protected path from one node S, to another node Z in the network:
1) Use Dijkstra""s SPT algorithm to find the shortest path between the source node S and the destination node Z (410).
2) For the shortest path found in step 1, determine which path segments contained in the path are not protected (420).
3) For each unprotected path segments identified in step 2, attempt to find an alternate edge disjoint path segment (430). An alternate edge disjoint path segment is one that follows a different and disjoint path, yet shares the same two terminal nodes as that of the primary segment.
4) If an edge disjoint segment cannot be found for each unprotected path segment, discard the shortest path found in step 1 (440), continue Dijkstra""s algorithm to find the next shortest path between nodes S and Z (450).
5) Define the protected paths (460). Define as protected those paths for which each of the unprotected segments found in step 2 have an alternate edge disjoint path segment.
It is not uncommon however, for the shortest path determined by Dijkstra""s algorithm to contain path segments which are not only unprotected, but which are also unprotectable. That is, edge disjoint path segments cannot be found or do not exist for those unprotected path segments, and thus those path segments cannot be protected (i.e. are unprotectable). In this case, since an alternate path cannot be found for at least one unprotected path segment in the path, the path itself cannot be protected and should not be used where protection is required. The path must be discarded from consideration and another path must be searched for. This proves inefficient and wasteful in that valuable time and computational resources are used to search for alternate edge disjoint paths even though no such alternate path exists. A new shortest path must also be computed because the shortest path found initially is discarded for lack of protectability. This cycle could be wastefully repeated numerous times until a protectable path is found.
For the foregoing reasons, there is a need for a method whereby unprotectable paths can be identified and excluded from consideration when determining the shortest protected path. The ability to exclude unprotectable paths and consider only those paths that are protectable prior to searching for edge disjoint alternate paths will significantly enhance the speed at which path protected network routing and circuit provisioning is effected.
The invention comprises a new and improved method for computing the shortest protectable paths in communication networks, and an improved method for establishing and defining protected paths. For automated routing of unidirectional or bi-directional protected circuits in SONETs or other switched networks, Dijkstra""s algorithm is used to find the shortest path between two network elements. Then, for each (primary) path segment that is not protected an alternate path segment is identified to accommodate path protection. Because there could be unprotected path segments which do not have alternate and edge disjoint path segments, such path segments are excluded from consideration in routing the shortest path in the case of required path protection.
It is an object of the invention to identify and exclude from further consideration, shortest paths which are unprotectable when computing the shortest path in network routing. To this end, it is also an object of the invention to identify and exclude unprotectable path segments and unprotectable links.
It is a further object of the invention to enable a more rapid determination of shortest protected paths leading to more rapid routing of network paths and increased network efficiency. It is a further object of the invention to improve the efficiency of and reduce the computational resources required for routing protected paths within communication networks.
The invention utilizes a new algorithm to exclude from consideration as the xe2x80x9cshortest pathxe2x80x9d between two network elements, a path for which adequate protection cannot be established. Because there are additional computational steps in defining the protected paths after the shortest path has been found, and because some of the shortest paths found will be unprotectable, consideration of unprotectable paths when attempting to define protected paths will be in vain and wasteful of resources. An unprotectable path can be identified and excluded because an unprotectable path contains one or more unprotectable links, and these unprotectable links can be identified and excluded based upon whether or not the link is a member of a loop. This initial exclusion of unprotectable paths from consideration eliminates this potential waste of resources and speeds up the computation efficiency in network path routing.
These and other features and objects of the invention will be more fully understood from the following detailed description of the preferred embodiments which should be read in light of the accompanying drawings.